package com.exercise;

import java.util.Random;

//跳跃游戏
public class Test1 {

    public static void main(String[] args){
        Test1 test = new Test1();
        Random rand = new Random();
        int count = 100000;
        int numRange = 1000000;
        int[] nums = new int[count];

        for(int i = 0;i < count; i ++){
            nums[i] = rand.nextInt(numRange);
        }
        long before = System.currentTimeMillis();
        System.out.println(test.canJump(nums));
        long after = System.currentTimeMillis();

        System.out.println(after - before);

    }

    public boolean canJump(int[] nums) {

        int endIndex = nums.length - 1;

        return canJumpTo(nums,endIndex);
    }

    private boolean canJumpTo(int[] nums, int endIndex) {

        if(endIndex == 0){
            return true;
        }

        boolean flag = false;
        for(int i = 0; i < endIndex; i++){
            if(nums[i] >= endIndex - i){
                flag = canJumpTo(nums,i);
            }
            if(flag){
                return true;
            }
        }

        return  flag;

    }
}
